package code1.binary_tree;

import java.util.*;

/**
 * 原题链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/
 */
public class P501 {

    //一般思想(对任意二叉树)：遍历一遍二叉树，用map统计每个数出现的频率，然后进行排序，取出频率最高的即为众数

    //key——结点的值,value——该值在在树中出现的次数
    private Map<Integer,Integer> map=new HashMap<>();

    //遍历二叉树（先序)
    public void travel(TreeNode root){
        if(root==null){
            return;
        }
        if(map.get(root.val)==null){
            map.put(root.val, 1);
        }else{
            map.put(root.val, map.get(root.val)+1);
        }
        travel(root.left);
        travel(root.right);
    }

    public int[] findMode(TreeNode root) {
        travel(root);
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        List<int[][]> list=new ArrayList<>();
        for(Map.Entry<Integer, Integer> entry:entries){
            int[][] pair=new int[1][2];
            pair[0][0]=entry.getKey();
            pair[0][1]=entry.getValue();
            list.add(pair);
        }
        list.sort(new Comparator<int[][]>() {
            @Override
            public int compare(int[][] o1, int[][] o2) {
                return o2[0][1]-o1[0][1];
            }
        });
        int max=list.get(0)[0][1];
        int count=0;
        for(int[][] pair:list){
            if(pair[0][1]==max){
                count++;
            }
        }
        int[] res=new int[count];
        for(int i=0;i<count;i++){
            res[i]=list.get(i)[0][0];
        }
        return res;
    }
}
